#ifndef BINARYTREE_H
#define BINARYTREE_H

#include <QDebug>

template<class T>
struct Node
{
    T value_;
    Node<T> *left_;
    Node<T> *right_;
};

template<class T>
class BinaryTree
{
public:
    BinaryTree()
    {
        this->root_ = 0;
    }

    BinaryTree(BinaryTree<T>& tree)
    {
        qDebug() << "copy constructor";
        this->initTree(tree.root_);
    }

    BinaryTree(const BinaryTree<T>& tree)
    {
        this->initTree(tree.root_);
    }

    BinaryTree(T value)
    {
        this->root_ = new Node<T>;
        this->root_->value_ = value;
        this->root_->left_ = 0;
        this->root_->right_ = 0;
    }

    ~BinaryTree()
    {
        this->destroyTree(this->root_);
    }

    int size()
    {
        return this->size(this->root_);
    }

    void initTree(Node<T> *other)
    {
        if(other == 0)
        {
            qDebug() << "trying to set a null root";
            return;
        }

//        if(this->root_ != 0)
//            this->destroyTree(this->root_);

        this->root_ = new Node<T>;
        this->root_->value_ = other->value_;
        this->root_->left_ = other->left_;
        this->root_->right_ = other->right_;
        qDebug() << "root set with value:" << this->root_->value_;
    }

    void add(T value)
    {
        if(this->root_ != 0)
            this->add(value, this->root_);
        else
        {
            this->root_ = new Node<T>;
            this->root_->value_ = value;
            this->root_->left_ = 0;
            this->root_->right_ = 0;
        }
    }

    bool remove(T value)
    {
        bool removed = false;
        if(this->root_ != 0)
        {
            Node<T> *removedNode;
            if(value == this->root_->value_)
            {
                Node<T> *temp = new Node<T>;
                temp->left_ = this->root_;
                removedNode = this->remove(value, this->root_, temp);
                this->root_ = temp->left_;
            }
            else
                removedNode = this->remove(value, this->root_, 0);
            if(removedNode != 0)
            {
                qDebug() << "Removing node: " << removedNode->value_;
                delete removedNode;
                removedNode = 0;
                removed = true;
            }
        }
        else
            qDebug() << "Binary tree empty, nothing to remove";
        return removed;
    }

private:

    int size(Node<T> *node)
    {
        int size = 0;
        if(node != 0)
        {
            size += 1;
            size += this->size(node->left_);
            size += this->size(node->right_);
        }
        return size;
    }

    void add(T value, Node<T> *node)
    {
        if(value < node->value_)
        {
            if(node->left_ != 0)
                this->add(value, node->left_);
            else
            {
                node->left_ = new Node<T>;
                node->left_->value_ = value;
                node->left_->left_ = 0;
                node->left_->right_ = 0;
            }
        }
        else // value >= node->value_
        {
            if(node->right_ != 0)
                this->add(value, node->right_);
            else
            {
                node->right_ = new Node<T>;
                node->right_->value_ = value;
                node->right_->left_ = 0;
                node->right_->right_ = 0;
            }
        }
    }

    Node<T> * remove(T value, Node<T> *node, Node<T> *parent)
    {
        Node<T> *removed = 0;
        if(value < node->value_)
        {
            if(node->left_ != 0)
                removed = this->remove(value, node->left_, node);
        }
        else if(value > node->value_)
        {
            if(node->right_ != 0)
                removed = this->remove(value, node->right_, node);
        }
        else // value == node->value_
        {
            if(node->left_ != 0 && node->right_ != 0)
            {
                node->value_ = this->minValue(node->right_);
                removed = this->remove(node->value_, node->right_, node);
            }
            else if(parent->left_ == node)
                parent->left_ = (node->left_ != 0) ? node->left_ : node->right_;
            else if(parent->right_ == node)
                parent->right_ = (node->left_ != 0) ? node->left_ : node->right_;
            removed = node;
        }
        return removed;
    }

    void destroyTree(Node<T> *node)
    {
        if(node != 0)
        {
            this->destroyTree(node->left_);
            this->destroyTree(node->right_);
            delete node;
            node = 0;
        }
    }

    T minValue(Node<T> *node)
    {
        return node->left_ == 0 ? node->value_ : this->minValue(node->left_);
    }

private:
    Node<T> *root_;
};

#endif // BINARYTREE_H
